package com.sunny.example.dynamicschedule;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 购物清单
 */
public class DS4 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int money = scanner.nextInt();
            int lines = scanner.nextInt();
            Goods[] gs = new Goods[lines + 1];
            List<Goods> mainGoods = new ArrayList<>();//主件
            for (int i = 1; i <= lines; i++) {
                Goods goods = new Goods();
                goods.v = scanner.nextInt();
                goods.p = scanner.nextInt();
                goods.q = scanner.nextInt();
                if (goods.q == 0) {
                    //主件
                    mainGoods.add(goods);
                }
                gs[i] = goods;
            }

            for (Goods g : gs) {
                if (g == null) continue;
                if (g.q > 0) {
                    Goods main = gs[g.q];
                    int index = mainGoods.indexOf(main);
                    if (index < 0) continue;
                    mainGoods.get(index).addSubGoods(g);
                }
            }

            for (int k=0;k<mainGoods.size();k++){
                Goods main = mainGoods.get(k);
                //如果总价超出预算，则放弃,从列表中移除
                //移除规则：
                //如果有2个附件，则先移除1个附件，移除重要度小的那个
                //如果还是大，则继续移除第2个附件
                if (main.v > money && mainGoods.contains(main)) {
                    mainGoods.remove(main);
                }
                if (main.getSubV() > money) {
                    mainGoods.get(k).subGoods.clear();
                }
                mainGoods.get(k).getMainSub(money);
            }

            int[][] dp = new int[mainGoods.size() + 1][money + 1];
            //使用动态规划寻找状态切换公式
            for (int i = 0; i <= mainGoods.size(); i++) {
//                dp[i][0] = 0;
                for (int j = 1; j <= money; j++) {

                    dp[0][j] = /*j>=curV?mainGoods.get(i).getP():*/0;
                    if (i >= 1 ) {
                        int curV = mainGoods.get(i-1).getTotalV();//当前商品的价格
                        int curP = mainGoods.get(i-1).getP();//当前商品重要程度
                        if (j >= curV) { //当前商品总价格小于列所在价格
                            //从1开始
                            dp[i][j] = Math.max(dp[i - 1][j], curP + dp[i - 1][j - curV]);
                        } else if (j < curV) {//当前商品大于列所在价格
                            dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
                        }

                    }
                }
            }

            System.out.println(dp[mainGoods.size()][money]);
        }

    }

    static class Goods {
        public int v;//单价
        public int p;//重要级别
        public int q;//编号，0：表示主件，>0为对应主件所在的索引

        //有些主件有附件，还可能有1个或2件附件
        List<Goods> subGoods = new ArrayList<>();

        public void addSubGoods(Goods goods) {
            if (subGoods.size() < 2) {//最多2件
                subGoods.add(goods);
            }
        }

        public int getP() {
            //附件
            int subP = 0;
            for (Goods g : subGoods) {
                subP += g.p * g.v;
            }
            return subP + p * v;

        }

        public int getTotalV() {
            int result = 0;
            for (Goods g : subGoods) {
                result += g.v;
            }
            return result + v;
        }

        public void getMainSub(int target) {
            if (subGoods.size() > 0) {
                int temp = v;
                for (int i = 0; i < subGoods.size(); i++) {
                    int subV = subGoods.get(i).v;
                    temp += subV;
                    if (temp > target) {
                        subGoods.remove(i);
                        temp -= subV;
                    }
                }
            }
        }

        /**
         * 获取附件的价格
         *
         * @return
         */
        public int getSubV() {
            int result = 0;
            for (Goods g : subGoods) {
                result += g.v;
            }
            return result;
        }
    }
}
